Thread: QuickSort — C Implementation (Non-Recursive)

Hi, I was anticipating if someone could give me some constructive feedback on the code below (not something like "don't use pointers" or "always use braces with loops or conditions", more like, "there is problem in the algorithm", or "this could be a better approach/algorithm", or "error in the code"). No offense to anyone. I'm here to learn. Thanks.

Code:

#include <stdio.h>

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}


void reversearray(int* arr, int size)
{
	for (int i = 0; i < size / 2; i++) swap(arr + i, arr + ((size - 1) - i));
}

int partitionarray(int* arr, int start, int end)
{
    int pivot = arr[end];
    int pIndex = start;
    for (int i = start; i < end; i++)
    {
        if (arr[i] <= pivot) swap(&arr[i], &arr[pIndex++]);
    }
    swap(&arr[pIndex], &arr[end]);
    return pIndex;
}




void quicksort(int* arr, int start, int end,  _Bool reverse)
{
    if (start < end)
    {
        int pIndex = start;
        while (pIndex < end) pIndex = partitionarray(arr, start, pIndex + 1);
        if (reverse) reversearray(arr, end + 1);
    }
}


int main()
{
    int arr[] = { 8, 5, 9, 0, 6, 4, 3, 7, 1, 2 };
	int size = sizeof(arr) / sizeof(arr[0]);
	quicksort(arr, 0, size - 1, 1);
	for (int i = 0; i < size; i++) printf("%d ", arr[i]);
	return 0;
}

Originally Posted by laserlight

Furthermore it looks like you don't start with the whole array when doing the first iteration of partitioning? It looks almost as if you're doing a variant of bubble sort instead.

Just suggesting nothing else
As he doesn't use the whole array, I suggest him instead of using bubble sort which is dramatically increasing the burst time of the code, he can use "binary search recursively/iterative" for finding the pivot o(logn) and then by for loop he can run on the array according to the pivot which will take o(n), in total o(nlogn) instead of bublesort which takes o(n^2).

Thank you! Well, I wanted to try something like python's sorted(iterable[, key][, reverse]) without the key parameter.

Thanks @laserlight. It didn't start with the whole array, and now it seems like it is replicating a bubble-sort. Could you give an example how can I use explicit stack to make this actual qucksort without recursion?

well, thanks for useful feedback. Will try that.